/**
 * com.future CO.,ltd.
 */

package com.future.mashibing.binary;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 类说明：
 */
public class Test01 {

    public static void main(String[] args) {

        int k = 5;
        int m = 8;
        int[] arr = getRandomArr(10, 1000, k, m);
        onlyKTImes(arr, k, m);
        //oddNumber();
        //rightestOne();

        //getTwoOddNum(new int[]{3, 3, 3, 1, 1, 1, 2, 2, 5, 5, 5, 5, 8, 8});
        //getBinaryOneCoun(152);
        // int arr[] = {1, 1, 2, 2, 2, 3, 3, 3};
        arr = new int[]{90, 90, 2, 2, 2, 22, 22, 22, 111, 111, 111};
        arr = new int[]{1, 1, 2, 2, 3};
        //onlyKTImes(arr, 1, 2);
    }

    /**
     * 怎么把int类型数，提取最右侧的1
     */
    private static void rightestOne() {
        int num = 10;
        /**
         * 00001010 相当于提取最右侧的1出来，即00001010
         * 过程
         * 00001010
         * 11111010-->~10+1
         * =
         * 00000010=2
         */
        System.out.println(num & (~num + 1));
    }

    /**
     * 一个数组中有两种数出现了奇数次，其他都出现了偶数次，怎么找到并打印这两个数(假设为a,b)
     */
    private static void getTwoOddNum(int[] arr) {
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        /**
         * eor <==> a^ b
         * eor必然有一个位置上是1
         */
        int rightOne = eor & (~eor + 1);//提取最右的1
        int onlyOne = 0;
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & rightOne) != 0) {
                onlyOne ^= arr[i];
            }
        }
        System.out.println(onlyOne + " ," + (eor ^ onlyOne));
    }

    /**
     * 计算二进制的1有几个
     * 如：10=00000110有三个1
     * <p>
     * 00000110
     * <p>
     * 00000010
     */
    private static void getBinaryOneCoun(int num) {
        int count = 0;
        // 求最右侧的1
        int rightOne;
        while ((rightOne = num & (~num + 1)) > 0) {
            num = num ^ rightOne;
            count++;
        }
        System.out.println(count);
    }

    /**
     * 一个数组中，只有一个数出现奇数次，其他都是偶数次，求这个出现奇数次的数
     */
    private static void oddNumber() {
        Integer[] arr = {2, 2, 2, 2, 3, 3, 11, 11, 4, 4, 4};
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        System.out.println(eor);
    }

    /**
     * 注意：当a、b都是指向同一个内存地址时，就不行
     * 因为第一次a^b就等于0了，以后的操作都是在一系列0的操作 都为0
     * 如果地址不一样，那就在不同的地址上操作，互不影响
     *
     * @param a
     * @param b
     */
    private static void swap(int a, int b) {
        System.out.println(a);
        System.out.println(b);
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
        System.out.println(a);
        System.out.println(b);
    }

    /**
     * 一个数组中有一种数出现K次，其他都出现了M次(K>1,K<M)
     * 找到出现了K次的数
     * 要求，额外空间复杂度O(1)，时间复杂度O(n)
     * 思路：给个实例，草稿写一下就明白了
     */
    private static void onlyKTImes(int[] arr, int k, int m) {
        int[] t = new int[32];
        // t[0] 的1出现了几个
        // t[i] 的1出现了几个
        for (int num : arr) {
            for (int i = 0; i < 32; i++) {
                t[i] += (num >> i) & 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            if (t[i] % m != 0) {
                ans |= (1 << i);
            }
        }
        // return ans;
        System.out.println(ans);
    }

    /**
     * 随机生成最大值为maxValue,只有一个数出现k次，其余都是出现m次的数组
     *
     * @param maxLength
     * @param maxValue
     * @param k
     * @param m
     * @return
     */
    private static int[] getRandomArr(int maxLength, int maxValue, int k, int m) {
        if (k >= m) {
            m++;
        }
        int size = (int) (Math.random() * maxLength + 1);
        int[] res = new int[k + size * m];
        int kValue = (int) (Math.random() * maxValue + 1);
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < k; i++) {
            res[i] = kValue;
        }
        set.add(kValue);
        for (int i = 0; i < size; i++) {
            int mValue = 0;
            do {
                mValue = (int) (Math.random() * maxValue + 1);
            } while (set.contains(mValue));
            for (int j = 0; j < m; j++) {
                res[k++] = mValue;
            }
            set.add(mValue);
        }
        System.out.println(Arrays.toString(res));
        return res;
    }
}
